It is often necessary to send data between devices in a computer system, for example it is often necessary to connect a processing device to a plurality of input and output devices. Appropriate data communication is achieved by connecting the devices in such a way as to allow them to send data to one another over a physical link, which may be a wired link or a wireless link.
It is known in the art to use a switch to route data from the outputs of one or more devices to inputs of one or more other devices. Such a switch comprises one or more ingress ports arranged to allow the data to be received by the switch, and one or more egress ports arranged to allow the data to be transmitted from the switch.
Circumstances may arise where particular data cannot be transmitted from the switch. This may occur where there is insufficient bandwidth or credit on a connecting link or where a receiving device is busy processing previously received data such that data received at a switch cannot be sent from the switch to a receiving device through the appropriate egress port. Switches may therefore contain a buffer to store data packets waiting to be transmitted from the switch through an appropriate egress port. It is known to store data packets in such a buffer in the form of one or more queues, which temporarily store data packets received from a sending device until those data packets can be sent to a receiving device. These buffers often comprise memory arranged as FIFO (first in, first out) queues.
The problems and complexities of data switch design are well known in the networking and data communication art. There are many conflicting requirements that make the perfect all-purpose solution impractical to achieve. Such conflicting requirements include the need for high link speeds, the need for minimal or zero loss of data, the need for maximal throughput to achieve high bandwidth utilisation, the need for fairness in the allocation of resources, the need for controllable quality of service, the need for scalability of design, and the need to minimise cost through minimising design resources and complexity. Typically, optimising performance conflicts with minimising cost, so that design compromises need to be made based on specific application requirements.
Shared input/output (I/O) is one application for data switching. Sharing of I/O devices can lead to better resource utilisation, scalability, ease of upgrade, and improved reliability. Since cost saving is a major driver in the acceptance of I/O sharing, it is important that the cost of the data switch is minimised to ensure the cost of the switch does not offset the cost advantages provided by I/O sharing. A significant challenge faced in the design of shared I/O switches is to minimise the cost of the switch while balancing the other requirements described above.
One type of commonly used switching technology is the crossbar switch. A crossbar switch is a non-blocking switch fabric capable of connecting N inputs to N outputs across a switch core in any one-to-one combination. That is, any input may be connected to any non-busy output. Inputs are connected to the outputs via a matrix of input and output lines with switches where the lines cross.
Where data packets received at a switch are buffered, at a particular time there is a need to select a data packet to be forwarded to the relevant egress port, and a further need to schedule when a selected data packet should be forwarded. A switch design should ideally maximize the use of the switch core (that is, maximise the number of cells that are switched in each timeslot) while ensuring that data packets are forwarded in a way that is fair, in the sense that all connections through the switch are given an equal opportunity to transfer data. These requirements are sometimes made more difficult by the need to support varying link rates between different ingress and egress ports. In many current switch designs, the selection of data packets for forwarding, and their scheduling is carried out in a single operation.
In order to enhance efficiency, many switches operate using fixed sized cells. Data which is to be transmitted through the switch is often encapsulated in one or more such cells for transfer through the switch from an input to an output. The use of fixed sized cells allows efficiency to be improved given that a switch core can be designed to optimally transfer the fixed quantity of data in a particular time slot. Where data packets of variable size are received at a switch, these data packets may be encapsulated in one or more fixed size cells by components of the switch to enable transfer through the switch.
While the use of fixed size cells can improve the efficiency of a switching device there remains a need for a switch which can efficiently and effectively process received data packets, and more particularly a switch which can effectively select data packets to be forwarded to a relevant egress port, and efficiently schedule the forwarding of a selected data packet.